package sun.cn.common.sunlaDfa.core;

import java.util.Arrays;
import java.util.List;
import java.util.Map;

import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.StringUtils;

import com.alibaba.fastjson.JSON;
import com.google.common.base.Stopwatch;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;

/**
 * DFA 有限自动机器
 * <p>通过字符的首字母构建索引列表</p>
 * @author sunla
 * @date 2017年4月3日
 * @version 1.0
 */
public final class SunlaDFA {
	
	private final Node entity;
	
	private final static int ARRNUM = 2;
	
	/**
	 * @author sunla
	 * @date 2017年4月3日
	 * @version 1.0
	 * @param arr
	 */
	private SunlaDFA(String[][] arr){
		entity = init(arr);
	}
	
	private final Node init(String[][] arr){
		if(arr == null || arr.length == 0)
			throw new NullPointerException("arr is null");
		Node node = new Node();
		Stopwatch watch = Stopwatch.createStarted();
		calculate(arr,node);
		System.out.println(String.format("create node list is %s", watch.toString()));
		return node;
	}
	
	/**
	 * <p>切分字符串,每次以第一个char为索引,
	 * <br>
	 * 查找以该char开头的字符串
	 * </p>
	 * @param arr 输入字符串数组
	 * @param node 递归节点
	 */
	private final void calculate(String[][] arr,Node node){
		Map<Character,Entity> tmp = Maps.newHashMap();
		Map<Character,List<Node>> calcRes = Maps.newHashMap();
		for(String[] info : arr){
			String key = info[0];
			String value = info[1];
			if(key == null)
				continue;
			char c = key.charAt(0);
			/** 寻找首字母数组 */
		    Entity entity = tmp.get(c);
		    /** 标记索引字符每次递归就截取掉第一个字符 ex:beijing -> eijing -> ijing -> jing -> ing .. */
		    if(key.length() > 0){
			entity = put(entity,c, key.length()>1?key.substring(1):null, value,arr.length);
			tmp.put(c, entity);
		    }
		}
		/** 递归处理 */
		for(Character c : tmp.keySet()){
			Entity entity = tmp.get(c);
			if(entity == null)
				continue;
			Node cnode = new Node(entity);
			String[][] enarr = entity.getArr();
			calculate(enarr,cnode);
			List<Node> list = calcRes.get(c);
			if(list == null)
				list = Lists.newArrayList();
			list.add(cnode);
			calcRes.put(c, list);
		}
		node.setResult(calcRes);
	}
	
	/**
	 * 寻找数组中为空的下一节点,并赋值
	 * @param arr 数组
	 * @param key 需切分的字符
	 * @param value 字符值
	 * @return
	 */
	private final Entity put(Entity entity,Character c,String key,String value,int size){
		if(entity == null){
			entity = new Entity(c, key, value, size);
		}
		final int length = entity.getArr().length;
		for(int i=0;i<length;i++){
			if(null == entity.getArr()[i][0]){
				entity.getArr()[i] = new String[]{key,value};
				entity.inc();
				break;
			}
		}
		return entity;
	}
	
	/**
	 * 查找匹配字符串
	 * <p>
	 * ex: 
	 * b -> beijing<br>
	 * be -> beijing<br>
	 * h -> hebei,henan,hubei,hunan<br>
	 * hu -> hubei,hunan<br>
	 * hub -> hubei<br>
	 * </p>
	 * @param str 待匹配字符串
	 * @return
	 */
	public Entity findByStr(String str){
		if(StringUtils.isBlank(str))
			return null;
		Stopwatch watch = Stopwatch.createStarted();
		Map<Character,List<Node>> param = entity.getResult();
		char[] cs = str.toCharArray();
		List<Node> list = param.get(cs[0]);
		int index = 1;
		while( index!=cs.length && list!=null){
			for(Node node : list){
				param = node.getResult();
				list = param.get(cs[index]);
			}
			index++;
		}
		System.out.println(String.format("spend time is %s", watch.toString()));
		return nodeConvertEntity(list);
	}
	
	private final Entity nodeConvertEntity(List<Node> list){
		Entity entity = null;
		if(list != null && !list.isEmpty()){
			entity = new Entity();
			for(Node node : list){
				entity.putArr(node.getEntity().getArr());
			}
		}
		return entity;
	}
	
	public String toString(){
		return JSON.toJSONString(entity);
	}
	
	public static SunlaDFA builder(String[][] arr){
		return new SunlaDFA(arr);
	}
	
	public static SunlaDFA builder(String[] arr){
		if(arr == null || arr.length == 0)
			throw new NullPointerException("arr is null");
		String[][] narr = new String[arr.length][ARRNUM];
		for(int i=0;i<arr.length;i++){
			narr[i] = new String[]{arr[i],arr[i]};
		}
		return new SunlaDFA(narr);
	}
	
	/**
	 * 节点元素
	 * @author sunla
	 * @date 2017年4月3日
	 * @version 1.0
	 */
	 private class Node {
		
		/** 存放每个key分析的索引列表 */
		private Map<Character,List<Node>> result;
		private Entity entity;

		public Node(){}
		
		public Node(Entity entity){
			setEntity(entity);
			/** 去掉数组中空元素 */
			this.entity.setArr(Arrays.copyOfRange(entity.getArr(), 0, entity.getArrRealSize()));
		}
		
		public Entity getEntity() {
			return entity;
		}
		
		void setEntity(Entity entity) {
			this.entity = entity;
		}

		public Map<Character, List<Node>> getResult() {
			return result;
		}

		 void setResult(Map<Character, List<Node>> result) {
			this.result = result;
		}
	}
	 
	/**
	 * 实体类
	 * 
	 * @author sunla
	 * @date 2017年4月3日
	 * @version 1.0
	 */
	public class Entity {

		private Character c;

		private String key;

		private String value;

		private String[][] arr;

		/** arr数组真实长度 */
		private int arrRealSize;

		public Entity(Character c, String key, String value, int size) {
			this.c = c;
			this.key = key;
			this.value = value;
			/** 初始化默认长度 */
			arr = new String[size][ARRNUM];
		}
		
		public Entity(){}
		
		int getArrRealSize() {
			return arrRealSize;
		}

		void inc() {
			arrRealSize++;
		}

		public String[][] getArr() {
			return arr;
		}

		void setArr(String[][] arr) {
			this.arr = arr;
		}

		public Character getC() {
			return c;
		}

		void setC(Character c) {
			this.c = c;
		}

		public String getKey() {
			return key;
		}

		void setKey(String key) {
			this.key = key;
		}

		public String getValue() {
			return value;
		}

		void setValue(String value) {
			this.value = value;
		}

		/**
		 * 扩充数组
		 * 
		 * @param arr
		 */
		void putArr(String[][] arr) {
			this.setArr(ArrayUtils.addAll(this.getArr(), arr));
		}
	}
}